Classifiers such as support vector machines (SVMs) can be employed for classification and regression of data sets. Classifiers are employed in many areas, including search, pattern recognition, regression estimation, “SPAM” detection, intrusion detection, and other security-related applications. An SVM operates by finding a hyper-surface in a space of possible inputs by analyzing training data. The hyper-surface attempts to split “positive” examples in the space of possible inputs from “negative” examples by maximizing the distance between the nearest of the positive and negative examples to the hyper-surface. This allows for correct classification of data that is similar, but not identical, to the training data.
Various techniques can be employed to train an SVM. Most commonly, a large portion of the training data is used to train the SVM, following which the remaining small portion of the training data is used to test the SVM's accuracy. This process is repeated until the test results in a satisfactory accuracy.
The training data can contain errors. For example, a provider of training data may maliciously or inadvertently provide training data that contains errors. A malicious entity that knows that a set of training data will be employed to train an SVM can purposely introduce errors in the training data so that, for example, a SPAM-detection component employing the resulting SVM classifies SPAM that the malicious entity later sends as not being SPAM. As an example, the malicious entity may be able to indicate that all electronic mail messages coming from an identified domain and containing a specified subject line are not SPAM. The behavior of the malicious entity may be difficult to understand and may not follow a well-defined model. This problem can be exacerbated when the training data comes from multiple sources, with some being potentially unreliable. As an example, a provider of anti-SPAM software may employ as training data electronic mail messages from several sources, with each such message identified as being SPAM or not SPAM. If one or more sources identify a large number of messages incorrectly, the resulting SVM could incorrectly classify messages it later receives. It is possible for a malicious source to alter a small subset of the training data to sufficiently alter the hyper-surface and thereby render it unusable.
Errors in the training data may not occur according to any known model. Thus, errors may be said to be correlated. Whether or not a data point is in error may depend on not just the data point itself, but on other data points as well. Alternatively, there may be no explicit malicious entity and consequently no explicit attack on the training data, in which case the errors may be said to be uncorrelated. In either case, the classification performance can significantly suffer because of the errors in the training data.